package com.example.leetcode.leetcode.hot100;

import com.example.leetcode.leetcode.tree.TreeNode;

import java.util.HashMap;
import java.util.Map;

/**
 * @author haitao
 * @date 2021/11/5 9:53 上午
 * 从前序与中序遍历序列构造二叉树
 * 给定一棵树的前序遍历 preorder 与中序遍历  inorder。请构造二叉树并返回其根节点。
 * preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
 * 通过递归分析确定（根节点，左子树集合，右子树集合），不断确定的是当前树根节点
 * preorder = [    根节点    ][           左子树              ][           右子树           ]
 *               preLeft    preLeft+1  pIndex-inLeft+preLeft pIndex-inLeft+preLeft+1  preRight
 * inorder = [           左子树              ][    根节点    ][           右子树           ]
 *          inLeft                  pIndex-1     pIndex     pIndex+1                 inRight
 *
 */
public class Solution105 {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length != inorder.length){
            return null;
        }
        // 中序节点遍历结果转Map
        Map<Integer,Integer> valueIndexMap = new HashMap<>(inorder.length);
        for (int i = 0; i < inorder.length; i++) {
            valueIndexMap.put(inorder[i],i);
        }
        return  buildTree(preorder, valueIndexMap,0,preorder.length-1,0,inorder.length-1);
    }
    public TreeNode buildTree(int[] preorder,Map<Integer,Integer> valueIndexMap,int preLeft, int preRight,int inLeft,int inRight){
        if(preLeft > preRight || inLeft > inRight){
            return null;
        }
        // 根节点
        TreeNode root = new TreeNode(preorder[preLeft]);
        int pIndex = valueIndexMap.get(preorder[preLeft]);
        root.left = buildTree(preorder,valueIndexMap,preLeft+1,pIndex-inLeft+preLeft,inLeft,pIndex-1);
        root.right = buildTree(preorder,valueIndexMap,pIndex-inLeft+preLeft+1,preRight,pIndex+1,inRight);
        return root;
    }
}
